ZK-SNARKs ピノキオプロトコル
問題の変換
前章まで
$ x^3 +x + 5 == 35 を満たすx (x=3)を知っていることを証明する
↓
X(X-1)(X-2)(X-3)で割り切れるような多項式P(X)を知っていることを証明する。
ただし、P(X)は、変数の正解の値のベクトルc( c=(1,3,35,9,27,30) )から生成された多項式L(X), R(X), O(X)を用いて、
$ P(X) = L(X) * R(X) - O(X)
とかける。
「割り切れる」多項式
$ T(X) = X(X-1)(X-2)(X-3)とおくと、この問題はさらにこう書き直せる。
$ P(X) = H(X)T(X)を満たすような$ P(X),H(X)を知っていることを証明する。
多項式の評価への変換
多項式が左右で一致するためには、Xの全ての取りうる値について計算した値が左右について一致すればよい。従って、この問題はさらにこう書き直せる。
全ての$ s \in \mathbb{F}_pについて$ P(s)= H(s)T(s)が成り立つような$ P(X),H(X)を知っていることを証明する。
実際には、多項式が左右で異なるのに代入した値が異なる確率はとても低いため、いくつかのsについて計算すれば十分である。
多項式のブラインド評価
Aliceは、正解の値のベクトルcからL(X),R(X),O(X)を生成し、T(X)で割ってH(X)を生成する。
Bobは、$ s \in \mathbb{F}_pをランダムに選び、E(T(s))を計算する。$ E(s),E(s^2),\cdotsをBobにAliceに送る。
Aliceは、それらからE(L(s)), E(R(s)), E(O(s))およびE((H(s))を計算する。Bobに結果を送る。
Bobは、Aliceから送られた結果からE(P(s))＝E((H(s)*T(s))が成り立っているかどうか確かめる。
⚠️以前考えたHH関数では、E(H(s)*T(s))はE(H(s))とE(T(s))から計算できない。Eとして、楕円曲線関数を使う。
⚠️多項式で計算したことを検証するために、Bobは、$ E(s),E(s^2),\cdotsだけでなく、$ \alpha \in \mathbb{F}_p^*を選んで$ E(\alpha* s),E(\alpha* s^2),\cdotsも送る。
Aliceが、正しい手法に従って多項式P(X)を生成したかどうか
動機
$ L(X) = \bold L_{X}\cdot \bold c = \sum_{j=0}^{5} c_i L_i(X)
のように、$ Lは$ L_iの係数を$ c_iとする線型結合でかける($ R(X),O(X)も同様)。ここで$ L_i, R_i, O_iは既知で、$ c_iが証明すべき値である。
しかり、Aliceが用いた$ Lは本当に$ L_iの線型結合で用いたものか分からないので、証明しなければならない。
手法
L,R,Oの多項式の次数の最大値をdとおいて、
$ F = L + R * X^{(d+1)} + O * X^{2(d+1)}
を考える。すると、F(X)の係数にはL(X),R(X),O(X)の係数がd+1次ずつに現れる。(0~d次にL(X), d+1~2d+1次にR(X), 2d+2~3d+2にO(X)の係数)
$ F_i = L_i + R_i* X^{(d+1)} + O_i * X^{2(d+1)}
と定義すると、
$ F = \sum_{j=0}^{5} c_i F_i
のように、$ Fは$ F_iの線形結合でかける。
$ Fを2通りの方法で記述できたので、
Bobは$ \beta \in \mathbb{F}_p^*を選んで、$ E(\beta*F_0(s)),E(\beta*F_1(s)),\cdots,E(\beta*F_5(s))をAliceに送る。
Aliceはこれらの値から$ E(\beta*F(s)) = E(\beta* \sum_{j=0}^{5} c_i F_i(s))を計算する。
送られてきた$ E(\beta*F(s))が、Aliceから送られてきた$ E(L(s)), E(R(s)), E(O(s))から計算したものと等しければ、Aliceの用いた$ L,R,Oは$ L_i, R_i, O_iの線型結合(係数は$ c_i)で出来たものだと証明できる。(ここはゼロ知識性を付与したら違いそう・・・)
ゼロ知識性を付与
動機
Aliceが送るE(L(s))自体も秘匿したい。
なぜなら、$ P(X) = H(X)T(X)を満たすような多項式Pを生成する正解のベクトルcが複数ある場合、Bobは自らが持っているc'から$ L',R',O'および$ E(L'(s)) ,E(R'(s)) ,E(O'(s))を計算し、これがAliceから送られてきたものと一致すればAliceの持つcはc'に等しいという情報を得ることが出来る。Aliceは、Bobに対してこのような情報も得させたくない。
手法
このような事態を避けるために、$ L,R,Oをずらした$ L_z, R_z, O_zを用いる。
ランダムに選んだ$ \delta_1,\delta_2,\delta_3 \in \mathbb{F}_p^*を用いて
$ L_z=L+\delta_1*T, R_z=R+\delta_2*T, O_z=O+\delta_3*Tのように、Tの方向にずらすことで、用いられたcの情報を隠匿する。
これらを用いると、
$ L_z*R_z-O_z = L*R-O+(L*\delta_2+\delta_1*R+\delta_1*\delta_2*T-\delta_3)T
$ = (H + L*\delta_2+\delta_1*R+\delta_1*\delta_2*T-\delta_3) T
と変形できるため、$ H_z = H + L*\delta_2+\delta_1*R+\delta_1*\delta_2*T-\delta_3と置いて$ L,R,O,Hの代わりに$ L_z, R_z, O_z, H_zを送れば、BobはAliceが用いたcの情報を得ないまま、検証が正しいと認識する。
次章の内容
線形結合だけでなく積をサポートしたHH関数を使いたい。
今はAliceとBobで対話型の通信を行なっているが、一度ずつの通信でできるようにしたい。
これらは、楕円曲線関数を使うことにより達成できる。
参考